// https://leetcode.cn/problems/jump-game-ii/
/*
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。【注意：肯定可以到达最后一个节点】

思路：



*/
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int jump(vector<int> &nums)
	{
		int ans = 0;
        int start = 0;
        int end = 1;
        while (end < nums.size())
        {
            int maxPos = 0;
            for (int i = start; i < end; i++)
            {
                // 能跳到最远的距离
                maxPos = max(maxPos, i + nums[i]);
            }
            start = end;      // 下一次起跳点范围开始的格子
            end = maxPos + 1; // 下一次起跳点范围结束的格子
            ans++;            // 跳跃次数
        }
        return ans;
	}
};

int main(){
	Solution so;
	// vector<int> s1 = {5,9,3,2,1, 0,2,3,3,1, 0,0}; // 长度12
	vector<int> s1 = {1, 1, 1, 1, 1}; // 长度12
	// vector<int> s1 = {1, 2, 1, 1, 1}; // 长度12
	// vector<int> s1 = {7,0,9,6,9, 6,1,7,9,0, 1,2,9,0,3}; // 长度12
	// vector<int> s1 = {1,2}; // 长度12
	// vector<int> s1 = {1,2,3}; // 长度12
	int a = so.jump(s1);
	cout << a << endl;
	return 0;
}